package com.kaizen.leet136;

import java.awt.*;
import java.util.ArrayList;

/**
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,2,1]
 * 输出: 1
 * 示例 2:
 * <p>
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * 通过次数185,414提交次数277,338
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SolutionUndi {

    public static void main(String[] args) {
        int[] nums = new int[]{2, -1, 2, 4, 4, 100, 100, 700, 700, 30, 30, 90, 90, 5, 5, -133, -133};
        long start = System.currentTimeMillis();
        System.out.println(singleNumber3(nums));
        long end = System.currentTimeMillis();
        System.out.println(end - start);

        int a = 100;
        int b = 100;
        System.out.println(a^b);
    }

    /**
     * 思路3：使用异或位运算
     *
     * @param nums
     * @return
     */
    public static int singleNumber3(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result = num ^ result;
        }
        return result;
    }

    /**
     * 思路2: 第一次循环添加到 arrayList，
     * 然后使用思路一的方式判断它是不是唯一
     * 负数问题解决，但是超出时间限制，效率不行
     *
     * @param nums
     * @return
     */
    public static int singleNumber2(int[] nums) {
        ArrayList arrayList = new ArrayList<Integer>();
        int result = 0;
        for (int num : nums) {
            arrayList.add(num);
        }
        for (int i = 0; i < arrayList.size(); i++) {
            if (arrayList.indexOf(nums[i]) == arrayList.lastIndexOf(nums[i])) {
                result = (int) arrayList.get(i);
            }
        }
        return result;
    }

    /**
     * 思路1：使用字符串的 indexof() 还有 lastindexof() 方法
     * 如果两个值相等，说明他是唯一的，返回该数
     * 思路失败，没有考虑到负数的问题，
     *
     * @param nums
     * @return
     */
    public static int singleNumber1(int[] nums) {
        StringBuffer bf = new StringBuffer();
        //最后返回的结果
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {

            }
            bf.append(nums[i]);
        }
        for (char ch : bf.toString().toCharArray()) {
            if (bf.toString().indexOf(ch) == bf.toString().lastIndexOf(ch)) {
                result = Integer.parseInt(String.valueOf(ch));
            }
        }
        return result;
    }


}
